BZOJ 3131 淘金

发表于 | 更新于

Link

震惊！某ZZ OIer此题WA了半天竟是因为点击查看

Solution

感觉第一步是最难想的。。但看了题解之后又觉得是很显然的。。只是不敢想罢了。 因为数字乘积的个数比较少，离散化一下就可以开到一维状态里。 然后一切都明朗了。 然而WA了很长时间，竟然因为

  1. 101210^{12}居然是1313位数？？？？？？
  2. 把数字分解的时候中间变量写成了int？？？？

Tips

数据范围吓人的但是似乎比较显然的算法也不能不想。因为也许吓人的范围后面隐藏着一些可以减小范围的性质。 在可能爆int的题目中WA了，试试 

1
#define int int64

不要数错数字位数。。。23333

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include "lucida"
using std::sort;
using std::unique;
using std::lower_bound;
using std::priority_queue;
const int P=1000000007,MAXCOUNT=203491+11,MAXINSCNT=11026+11;
int64 nums[MAXCOUNT];int nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
void DFS(int pos,int maxNumber,int64 prod) {
	if(!pos) {
		nums[++nc]=prod;
	} else {
		for(int d=maxNumber;d<10;++d) {
			DFS(pos-1,d,prod*d);
		}
	}
}
void Prep() {
	nums[nc=1]=0;//数组开小愣是看不着 233
	DFS(13,1,1);
	sort(nums+1,nums+1+nc);
	nc=unique(nums+1,nums+1+nc)-nums-1;
}
struct Node {
	int64 val;
	int id,ext;
	Node(int64 val,int id,int ext):val(val),id(id),ext(ext) {}
	friend bool operator <(const Node &a,const Node &b) {
		return a.val<b.val;
	}
};
int main() {
	freopen("input","r",stdin);
	static int64 f[14][10][2][MAXINSCNT],g[MAXINSCNT];
	Prep();	
	int64 n;int K;is>>n>>K;
	//g[pos] 乘积为pos位置的个数
	int bit[14],len=0;
	for(int64 x=n;x;x/=10) {
		bit[++len]=x%10;
	}
	for(int d=1;d<=bit[len];++d) {
		f[len][d][d==bit[len]][ref(d)]=1;
	}
	for(int i=len-1;i;--i) {
		for(int d=1;d<10;++d) {
			f[i][d][0][ref(d)]=1;
		}
	}
	for(int i=len-1;i;--i) {
		for(int cd=1;cd<10;++cd) {
			for(int pd=1;pd<10;++pd) {
				for(int pu=0;pu<2;++pu) if(!(pu && bit[i]<cd)) {
					for(int prod=1;prod<=nc;++prod) if(f[i+1][pd][pu][prod]) {
						if(nums[ref(nums[prod]*cd)]!=nums[prod]*cd) {
							throw;
						}
						f[i][cd][pu && cd==bit[i]][ref(nums[prod]*cd)]+=f[i+1][pd][pu][prod];
					}
				}
			}
		}
	}
	for(int prod=2;prod<=nc;++prod) {
		for(int d=1;d<10;++d) {
			for(int u=0;u<2;++u) if(!(u && bit[1]<d)) {
				g[prod-1]+=f[1][d][u][prod];
			}
		}
	}
	nc--;
	sort(g+1,g+1+nc);
	priority_queue<Node> Q;
	for(int i=1;i<=nc;++i) {
		Q.push(Node(g[i]*g[nc],i,nc));
	}
	int64 Ans=0;
	for(int i=1;i<=K && !Q.empty();++i) {
		Node cur=Q.top();Q.pop();
		(Ans+=cur.val)%=P;
		if(cur.ext!=1) {
			Q.push(Node(g[cur.id]*g[cur.ext-1],cur.id,cur.ext-1));
		}
	}
	os<<Ans<<'\n';
	return 0;
}